#ifndef __KNAPSACKPROBLEM
#define __KNAPSACKPROBLEM

/*
* 贪心算法只能够解决部分的背包问题
* 只提供一些解题思路
*/

#include <vector>
#include <iostream>
using namespace std;

typedef struct KnapsackObject {
	int Weight;
	int Price;
	bool bInKnapsack;
}Object;

typedef struct Knapsack{
	vector<KnapsackObject> Objects;
	int Total;
}Knapsack;

/*
* 每次选择都根据最大价值进行选择
* 显然这种策略是不对的
* 反例：
* W=30
* w: 28 20 10
* p: 30 20 20
*/
int ChooseFuncByPrice(vector<KnapsackObject>& objs, int remainWeight) {
	int index = -1;
	int maxPrice = 0;
	for (int i = 0; i < objs.size(); i++) {
		//搜索最高价值 且 没有放入背包 的物品
		if (!objs[i].bInKnapsack && objs[i].Price > maxPrice) {
			//若物品超重, 不放入
			if (objs[i].Weight > remainWeight)
				continue;
			
			index = i;
			maxPrice = objs[i].Price;
		}
	}
	if (index != -1)
		objs[index].bInKnapsack = true;
	return index;
}

/*
* 每次选择都根据最小重量(量最多)
* 显然也不对
*/
int ChooseFuncByWeight(vector<KnapsackObject>& objs, int remainWeight) {
	int index = -1;
	int minWeight = INT32_MAX;

	for (int i = 0; i < objs.size(); i++) {
		if (!objs[i].bInKnapsack && objs[i].Weight < minWeight) {
			if (objs[i].Weight > remainWeight)
				continue;

			index = i;
			minWeight = objs[i].Weight;
		}
	}
	if (index != -1)
		objs[index].bInKnapsack = true;
	return index;
}

/*
* 每次选择都最大根据单位价值
* 也不对, 每个物品的单位价值可能相同
* W=30
* w：28 20 10
* p：28 20 10
* 这样也不对, 该序列放入 w = 28 之后, 就放不进去了
* 所以要序列先按照重量进行排序
*/

int ChooseFuncByUnitPrice(vector<KnapsackObject>& objs, int remainWeight) {
	int index = -1;
	float maxUnitPrice = 0.f;

	for (int i = 0; i < objs.size(); i++) {
		float unitPrice = float(objs[i].Price) / objs[i].Weight;
		if (!objs[i].bInKnapsack && unitPrice > maxUnitPrice) {
			if (objs[i].Weight > remainWeight)
				continue;

			index = i;
			maxUnitPrice = unitPrice;
		}
	}
	if(index != -1)
		objs[index].bInKnapsack = true;
	return index;
}


bool CompareKnapsackObjectByWeight(const KnapsackObject& obj1, const KnapsackObject& obj2) {
	return obj1.Weight < obj2.Weight;
}

bool CompareKnapsackObjectByPrice(const KnapsackObject& obj1, const KnapsackObject& obj2) {
	return obj1.Price < obj2.Price;
}

void PrintObjects(const vector<KnapsackObject>& objs) {
	for (const KnapsackObject& obj : objs) {
		cout << obj.Weight << " ";
	}
	cout << endl;

	for (const KnapsackObject& obj : objs) {
		cout << obj.Price << " ";
	}
	cout << endl;
}

#endif // !__KNAPSACKPROBLEM
